#include "type.h"

std::vector< std::set<int> > generate_subset(size_t subset_size,std::set<int>::iterator first,std::set<int>::iterator last)
{
	std::vector< std::set<int> > res ;
	if (subset_size == 0 ) {
		res.push_back(std::set<int>());
		return res;
	} else if (subset_size > std::distance(first,last) ) {
		return res ;
	}

	//pour chaque element, generer tout les sous-ensemble qui l'ont comme plus petit element
	for (auto it = first;it != last;++it) 
	{
		auto it2 = it;
		++it2;
		auto partial_subsets = generate_subset(subset_size - 1,it2,last);
		std::for_each(partial_subsets.begin(),partial_subsets.end(),[&](std::set<int> &subset) {subset.insert(*it) ; });
		res.insert(res.end(),partial_subsets.begin(),partial_subsets.end());
	}
	return res;

}
void printSet(const std::set<int> & s,std::stringstream & c)
{
	c << "( ";
	std::for_each(s.begin(),s.end(),[&](int i) {c << i << " " ;} );
	c << ")" ;
}
//marche uniquement avec listS
void remove_vertices(const std::set<int> & vertices_to_remove,Graph &g,const std::map<int,Graph::vertex_descriptor> & descs = std::map<int,Graph::vertex_descriptor>())
{
	Graph::vertex_iterator vi, vi_end, next;
	boost::tie(vi, vi_end) = boost::vertices(g);
	for (next = vi; vi != vi_end; vi = next) {
		++next;
		if ( vertices_to_remove.find(g[*vi]) != vertices_to_remove.end()){
				boost::clear_vertex(*vi,g);
				boost::remove_vertex(*vi, g);
				}
	}
}
void keep_vertices(const std::set<int> & vertices_to_keep,Graph &g)
{
	Graph::vertex_iterator vi, vi_end, next;
	boost::tie(vi, vi_end) = boost::vertices(g);
	for (next = vi; vi != vi_end; vi = next) {
		++next;
		if ( vertices_to_keep.find(g[*vi]) == vertices_to_keep.end()){
			boost::clear_vertex(*vi,g);
			boost::remove_vertex(*vi, g);
		}
	}
}
//la qualite d'un sous-ensemble est le nombre d'arret que le sous graphe enleve si on le retire du graph
//somme des degree moin le nombre d'arrete qui relit deux point du sous-ensemble
int set_quality(const std::set<int> &vertices,const Graph & g,const std::map<int,Graph::vertex_descriptor> & descs) 
{
	int sum_degree = 0 ;
	std::for_each(vertices.begin(),vertices.end(),[&g,&sum_degree,&descs](int i){sum_degree+=boost::degree(descs.at(i),g);});
	std::set<Graph::vertex_descriptor> v;
	std::transform(vertices.begin(),vertices.end(),std::inserter(v,v.begin()),[&g,&descs](int i){return descs.at(i);});

	auto edges = boost::edges(g) ;
	auto pred = [&](Graph::edge_descriptor & edge){ 
		return ( v.end() != v.find(boost::source(edge,g)) && ( v.end() != v.find(boost::target(edge,g)) ) )   ; 
	};

	auto internal_edge_count = std::count_if(edges.first,edges.second,pred); 
	return sum_degree - internal_edge_count ;
}
struct detect_loops : public boost::dfs_visitor<>
{
  bool * loop_detected;
  std::map<Graph::vertex_descriptor,int> * involve_in_cycle;

  detect_loops(bool & loop_detected,
			   std::map<Graph::vertex_descriptor,int> & involve_in_cycle) 
  {
	  this->loop_detected = &loop_detected ;
	  this->involve_in_cycle = &involve_in_cycle ;
  };
  template <class Edge, class Graph>
  
  void back_edge(Edge e, const Graph& g) {
	(*loop_detected) = true ;
	(*involve_in_cycle)[boost::target(e,g)] += 1 ;
	(*involve_in_cycle)[boost::source(e,g)] += 1 ;
  }

};
void index_maps(const Graph & g,desc2int_t & desc2int,int2desc_t & int2desc)
{
	auto it = boost::vertices(g).first;
	auto end = boost::vertices(g).second;
	for(;it != end;++it)
	{
		desc2int.insert(std::make_pair(*it,g[*it]));
		int2desc.insert(std::make_pair(g[*it],*it));
	}

}
bool is_a_forest(Graph & g,
				 std::map<Graph::vertex_descriptor,boost::default_color_type> & v_color ,
				 std::map<Graph::edge_descriptor,boost::default_color_type> & e_color,
				 std::map<Graph::vertex_descriptor,int> & involve_in_cycle)
{

	auto vertices = boost::vertices(g);
	auto edges = boost::edges(g);

	for(auto it = vertices.first ; it != vertices.second; ++it){
		involve_in_cycle[*it] = 0;
	};

	
	bool loop_detected = false ;	
	detect_loops loop_detector(loop_detected,involve_in_cycle) ; 
	boost::associative_property_map< std::map<Graph::vertex_descriptor,boost::default_color_type> >  vertex_color(v_color);
	boost::associative_property_map< std::map<Graph::edge_descriptor,boost::default_color_type> >    edge_color(e_color);

	boost::undirected_dfs(g, boost::visitor(loop_detector).edge_color_map(edge_color).vertex_color_map(vertex_color));
	return !loop_detected ;
};


void print_graph_cycle(Graph g)
{
	std::map<Graph::vertex_descriptor,boost::default_color_type> v_color ;
	std::map<Graph::edge_descriptor,boost::default_color_type> e_color ;
	std::map<Graph::vertex_descriptor,int> involve_in_cycle ;
	std::map<int,Graph::vertex_descriptor>  useless ;

	auto vertices = boost::vertices(g) ;
	for (auto it = vertices.first; it != vertices.second;++it)
	{
		auto v_col = std::make_pair(*it,boost::white_color);
		auto cyl = std::make_pair(*it,0);
		v_color.insert(v_col);
		involve_in_cycle.insert(cyl);

	};
	auto edges = boost::edges(g);
	for (auto it = edges.first;it != edges.second;++it)
	{
		auto e_col = std::make_pair(*it,boost::white_color);
		e_color.insert(e_col);
	}

	is_a_forest(g,v_color,e_color,involve_in_cycle);
	auto cycle_to_color = [] (float value) -> std::string{
		auto h = boost::lexical_cast<std::string>(0.0);
		auto s = boost::lexical_cast<std::string>(1.000f);
		auto v = boost::lexical_cast<std::string>(1-value);
		std::stringstream ss ;
		ss <<"[style=filled,color=" "\""<< h << " " << s << " " << v << "\"]";
		return ss.str();
		;} ;

	std::stringstream ss ;
	ss << "Graph { \n" ;
	float max = std::max_element(involve_in_cycle.begin(),involve_in_cycle.end(),[](std::pair<Graph::vertex_descriptor,int> e1,std::pair<Graph::vertex_descriptor,int> e2){ return e1.second < e2.second ;})->second ;
	std::for_each(vertices.first,vertices.second,[&](Graph::vertex_descriptor vertex) { ss << g[vertex] << cycle_to_color(involve_in_cycle[vertex]/max) << std::endl ;});
	std::for_each(edges.first,edges.second,[&](Graph::edge_descriptor edge) { ss << g[edge.m_source] << " -- " << g[edge.m_target]  << std::endl ;});
	ss << "}\n";
	std::string name = "cycle" ;
	std::ofstream file(name+".dot");
	file << ss.str() ;
	file.close() ;
	std::system( ("dot -Tsvg "+name+ ".dot > " + name+".svg").c_str());
}
/*
void amelioration(Graph & org,Graph & forest)
{
	// on recherche des vertex qu'on peut rajouter
	// pour rajouter un vertex, il faut que aucun de ces voisins dans la forest ne soit connectec
	auto can_be_added  = [](Graph & org1,Graph & forest1){
	auto forest_vertices_ = boost::vertices(forest1);
	auto org_vertices_ = boost::vertices(org1);
	
	std::set<my_vertex_t> forest_vertices;
	std::set<my_vertex_t> org_vertices ;
	std::transform(forest_vertices_.first,
				    forest_vertices_.second,
					std::inserter(forest_vertices,forest_vertices.begin()),
					[&forest](Graph::vertex_descriptor v)mutable {forest[v];});
	} ;


}*/
void print_graph_stat(const Graph  & g)
{	auto vertices =  boost::vertices(g);
	auto vertex_count = std::distance(vertices.first,vertices.second);
	auto edges =  boost::vertices(g);
	auto edge_count = std::distance(edges.first,edges.second);
	std::cout << "vertex_count : " << vertex_count << ", edge_count : " << edge_count << std::endl;
	std::stringstream c ;
	draw_graph(g,c,"my_graph");
	std::cout << c.str() ;
}
//retire les noeud un a un par ordre de degree decroisasnt jusqu'a obtenir une foret
//TODO modifier pour toujours elever un node dans les composant ou ya au moin une boucle
int intensify(Graph & g) {
	int nb_interresting_vertices = 4 ;
	std::vector<std::map<Graph::vertex_descriptor,boost::default_color_type>> v_color_s(nb_interresting_vertices) ;
	std::vector<std::map<Graph::edge_descriptor,boost::default_color_type>> e_color_s(nb_interresting_vertices) ;
	std::vector<std::map<Graph::vertex_descriptor,int>> involve_in_cycle_s(nb_interresting_vertices) ;
	std::map<int,Graph::vertex_descriptor>  useless ;

	std::vector<Graph::vertex_descriptor> v_temps(boost::num_vertices(g));
	std::vector<int> interresting_vertices(boost::num_vertices(g));
	std::vector<Graph> voisinage(nb_interresting_vertices);
	
	//initialisation
	auto vertices = boost::vertices(g) ;
	for (auto it = vertices.first; it != vertices.second;++it)
	{
		auto v_col = std::make_pair(*it,boost::white_color);
		auto cyl = std::make_pair(*it,0);
		for (int i = 0 ; i < nb_interresting_vertices ;++i)
		{
			v_color_s[i].insert(v_col);
			involve_in_cycle_s[i].insert(cyl);
		};

	};
	auto edges = boost::edges(g);
	for (auto it = edges.first;it != edges.second;++it)
	{
		auto e_col = std::make_pair(*it,boost::white_color);

		for (int i = 0 ; i < nb_interresting_vertices ;++i)
		{
			e_color_s[i].insert(e_col);
		};
	}

	if (is_a_forest(g,v_color_s[0],e_color_s[0],involve_in_cycle_s[0]))
		return boost::num_vertices(g);
	Graph g1 = g ; //copy local de g;
	int selected_voisin = 0 ;
	while(true){
	//Construire le voisinage, le voisinage est un ensemble de graph obtenue a partir du graph courant en retirant certaitn vertices
	v_temps.clear();
	interresting_vertices.clear();
	vertices = boost::vertices(g1) ;
	v_temps.insert(v_temps.begin(),vertices.first,vertices.second);
	std::sort(v_temps.begin(),v_temps.end(),[&g1,&involve_in_cycle_s,&selected_voisin](Graph::vertex_descriptor x,Graph::vertex_descriptor y){
		return boost::degree(x,g1) > boost::degree(y,g1);
		//return involve_in_cycle_s[selected_voisin][x] > involve_in_cycle_s[selected_voisin][y] ;
	});
	
	auto end = (v_temps.size() <  nb_interresting_vertices) ? v_temps.end() : (v_temps.begin() + nb_interresting_vertices) ;
	std::transform(v_temps.begin(),end,std::back_inserter(interresting_vertices),[&g1](Graph::vertex_descriptor v){return g1[v];}); 
	//evaluation de chaque voisins
	int best_vertices_index = 0;
	float best_vertices_value = 1000000 ; //tres grande valeurs
	Graph best_subgraph ;	
	
	for (int i = 0 ; i< nb_interresting_vertices;++i)
	{
		Graph cp = g1 ;
		auto temp = std::set<int>();
		temp.insert(temp.begin(),interresting_vertices[i]);
		remove_vertices(temp,cp,useless);

		if (is_a_forest(cp,v_color_s[i],e_color_s[i],involve_in_cycle_s[i]))
		{
			g = cp ;
			return boost::num_vertices(g) ;
		};

		auto t = std::count_if(involve_in_cycle_s[i].begin(),involve_in_cycle_s[i].end(),[](std::pair<Graph::vertex_descriptor,int> e1){return e1.second > 0 ;});
		//auto t = *std::max_element(involve_in_cycle_s[i].begin(),involve_in_cycle_s[i].end(),[](std::pair<Graph::vertex_descriptor,int> e1, std::pair<Graph::vertex_descriptor,int> e2){return e1.second < e2.second;});
		//auto t = 0.0f;
		//for (auto it = involve_in_cycle_s[i].begin();it != involve_in_cycle_s[i].end();++it)
		//	t +=  it->second ;
		//t /= std::distance(involve_in_cycle_s[i].begin(), involve_in_cycle_s[i].end());
		auto voisin_quality = t ;//t.second ;
		if (voisin_quality < best_vertices_value){
			best_vertices_value = voisin_quality ;
			best_vertices_index = i ;
			//best_subgraph = cp ;
			//auto vertices = boost::vertices(cp) ;
			int count = 0 ;
			//std::cout << voisin_quality << " : " << boost::num_vertices(cp) << std::endl ;
			//std::cout << "Start Printing vectors" <<std::endl ;
			//for (auto it = vertices.first;it != vertices.second;++it,++count){
			//	std::cout << cp[*it] << " : "<< involve_in_cycle_s[i][*it]<< "\t" ;
			//	if ((count % 4) == 0)
			//		std::cout << std::endl ;
			//}
			//std::cout << std::endl << "End Printing vectors" <<std::endl ;
		}
	};

	//selection du meilleurs voisin
	selected_voisin = best_vertices_index ;
	auto temp = std::set<int>();
	temp.insert(temp.begin(),interresting_vertices[selected_voisin]);
	remove_vertices(temp,g1,useless);
}
	throw "Something strange" ;
	return boost::num_vertices(g);
}
Graph generate_random_graph(size_t order,size_t size) {
	Graph g;
/*	
	for (int i = 0 ; i < order; ++i)
			boost::add_vertex(g);
	auto vertices = boost::vertices(g);
	std::set<int> s(vertices.first,vertices.second);
	auto pairs = generate_subset(2,s.begin(),s.end());
	auto set_to_edge = [&](std::set<int> & s){return std::pair<int,int>(*s.begin(),*(++s.begin())) ; };
	//genere size nombre aleatoire
	std::set<int> p;
	srand(time(NULL));
	int max_edge = pairs.size() ;
	for (int i  = 0 ; i < size ; ++i){
		while(! p.insert(rand() % max_edge).second){}; //verifier les doublons
	}
	std::for_each(p.begin(),p.end(),[&](int i ) {auto a = set_to_edge(pairs[i]) ; boost::add_edge(a.first,a.second,g) ;});
*/
	return g;
};

/*
int exact_maximal_forest(Graph & g,desc2int_t & desc2int,int2desc_t & int2desc) 
{	auto f = [] (Graph  & g1, 
const std::set<int> &node_to_remove,
int2desc_t & int2desc) -> bool {
	remove_vertices(node_to_remove,g1,int2desc);
	
	return is_a_forest(g1);
};

//display_graph(g,"graph_original") ;

if (is_a_forest(g))
{
	std::cout << "already a forest" << std::endl ;
	return boost::num_vertices(g);
}

auto vertices = std::set<int>();
for(auto it = boost::vertices(g).first;it != boost::vertices(g).second;++it)
	vertices.insert(g[*it]);

int count = 0;
std::set<int> ensemble_trouver ;
Concurrency::critical_section c;

while(true)

{
	count++;

	auto subsets = generate_subset(count,vertices.begin(),vertices.end()) ;
	auto nb = std::distance(subsets.begin(),subsets.end()); 
	int tested = 0;
	//std::cout << "Testing  subset of : " << count << ", " << nb << "subsets " << std::endl ;
	
	//Parrallel version
	bool deja_trouver = false ;
	
	auto fun = [&deja_trouver,&ensemble_trouver,&g,&int2desc,&f,&c](std::set<int>  & s)
	{
		Graph cp = g ;
		if (deja_trouver == true)
			return ;
		bool temp = f(cp,s,int2desc) ;
		if (temp == true)
		{
			c.lock();
			deja_trouver = true;
			ensemble_trouver.clear();
			ensemble_trouver.insert(s.begin(),s.end()) ;
			c.unlock();
		};

	} ;
		
	Concurrency::parallel_for_each(subsets.begin(),subsets.end(),fun) ;
	
	if (deja_trouver == true){
		Graph temp = g ;
		remove_vertices(ensemble_trouver,temp,int2desc);
		//std::cout << "maximal_forest : " << (boost::num_vertices(g) - count) << std::endl ; 
		auto v = std::set<my_vertex_t>();
		std::transform(boost::vertices(temp).first,boost::vertices(temp).second,std::inserter(v,v.begin()),[&temp](Graph::vertex_descriptor a){ return temp[a] ;});
		auto e = std::set<my_edge_t>();
		std::transform(boost::edges(temp).first,boost::edges(temp).second, std::inserter(e,e.begin()),[&temp](Graph::edge_descriptor a){ return temp[a] ;});
		//display_graph(g,"maximal_forest",e,v) ;
		int res = (boost::num_vertices(g) - count);
		g = temp ;
		return res ;
	};
	////A retirer
	for(auto s = subsets.begin();s != subsets.end();++s)
	{
		auto temp = g ; 
		if (f(temp,*s,int2desc))
		{
			std::cout << "maximal_forest : " << (boost::num_vertices(g) - count) << std::endl ; 
			auto v = std::set<my_vertex_t>();
			std::transform(boost::vertices(temp).first,boost::vertices(temp).second,std::inserter(v,v.begin()),[&temp](Graph::vertex_descriptor a){ return temp[a] ;});
			auto e = std::set<my_edge_t>();
			std::transform(boost::edges(temp).first,boost::edges(temp).second, std::inserter(e,e.begin()),[&temp](Graph::edge_descriptor a){ return temp[a] ;});
			display_graph(g,"maximal_forest",e,v) ;
			return (boost::num_vertices(g) - count) ;
		};

	};
	//fin a retire
	
}

}
*/
